/**
 * Divide two integers without using multiplication, division and mod operator.
 * This problem is quite tricky!
 * Math.abs(Integer.MIN_VALUE) is negative! cause max poistive is 1 smaller than max negative
 */
package com.xinpan.exercise;

public class DivideTwoInt {
    public int divide(int dividend, int divisor) {
        // Start typing your Java solution below
        // DO NOT write main() function


    	long res = 0;
        int sign = (dividend >> 31) ^ (divisor >> 31);
        
        long dd = Math.abs((long)dividend);
        long div = Math.abs((long)divisor);
        
        
        long tmpdiv = div;
        while(dd >= div)
        {
        	tmpdiv = div;
        	long step = 1;
        	while(dd > (tmpdiv << 1))
            {
                if(tmpdiv > (tmpdiv << 1))
                	break;
                
                step += step;
                tmpdiv = (tmpdiv << 1);
            }
            
            for(;dd >= tmpdiv; res += step, dd -= tmpdiv);
        }
        
   
        if(sign != 0)
            return (int)(0 - res);
        else 
            return (int)res;
            
    }
    
    public static void main(String[] args)
    {
    	DivideTwoInt dti = new DivideTwoInt();
    	System.out.println(dti.divide(2, 2));
    }
}
